#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<functional>

using namespace std;

namespace lh
{
	//692. 前K个高频单词
	//https://leetcode.cn/problems/top-k-frequent-words/
    class Solution {
    public:
        vector<string> topKFrequent(vector<string>& words, int k) {
            map<string, int>Countmap;
            //map[]插入+修改实现统计
            for (auto& str : words)
            {
                Countmap[str]++;
            }
            //比较次数，我们把次数作为Key,降序排
            multimap<int, string, greater<int>>sortmap;
            for (auto& kv : Countmap)
            {
                sortmap.insert(make_pair(kv.second, kv.first));
            }
            vector<string>v;
            multimap<int, string, greater<int>>::iterator it = sortmap.begin();
            while (k--)
            {
                v.push_back(it->second);
                ++it;
            }
            return v;
        }
    };


    //349. 两个数组的交集
    //https://leetcode.cn/problems/intersection-of-two-arrays/
    class Solution2 {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            //找交集（有序）：小的往后走，相等找到存入并同时走
            set<int>s1(nums1.begin(), nums1.end());
            set<int>s2(nums2.begin(), nums2.end());

            auto it1 = s1.begin();
            auto it2 = s2.begin();
            vector<int>v;
            while (it1 != s1.end() && it2 != s2.end())
            {
                if (*it1 < *it2)
                {
                    ++it1;
                }
                else if (*it2 < *it1)
                {
                    ++it2;
                }
                else
                {
                    v.push_back(*it1);
                    ++it1;
                    ++it2;
                }
            }
            return v;
        }
    };
}

int main()
{
    return 0;
}